package top100.slidewindow;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

/**
 * @Author ZhangCuirong
 * @Date 2025/7/28 13:41
 * @description: 代码
 * 测试用例
 * 测试结果
 * 测试结果
 * 480. 滑动窗口中位数
 * 困难
 * 相关标签
 * premium lock icon
 * 相关企业
 * 提示
 * 中位数是有序序列最中间的那个数。如果序列的长度是偶数，则没有最中间的数；此时中位数是最中间的两个数的平均数。
 * <p>
 * 例如：
 * <p>
 * [2,3,4]，中位数是 3
 * [2,3]，中位数是 (2 + 3) / 2 = 2.5
 * 给你一个数组 nums，有一个长度为 k 的窗口从最左端滑动到最右端。窗口中有 k 个数，每次窗口向右移动 1 位。你的任务是找出每次窗口移动后得到的新窗口中元素的中位数，并输出由它们组成的数组。
 * <p>
 * <p>
 * <p>
 * 示例：
 * <p>
 * 给出 nums = [1,3,-1,-3,5,3,6,7]，以及 k = 3。
 * <p>
 * 窗口位置                      中位数
 * ---------------               -----
 * [1  3  -1] -3  5  3  6  7       1
 * 1 [3  -1  -3] 5  3  6  7      -1
 * 1  3 [-1  -3  5] 3  6  7      -1
 * 1  3  -1 [-3  5  3] 6  7       3
 * 1  3  -1  -3 [5  3  6] 7       5
 * 1  3  -1  -3  5 [3  6  7]      6
 * 因此，返回该滑动窗口的中位数数组 [1,-1,-1,3,5,6]。
 */
public class Solution480 {
    public double[] medianSlidingWindow(int[] nums, int k) {
        List<Double> res = new ArrayList<>();
        // 大根堆，维护较小的一半元素
         PriorityQueue<Integer> small = new PriorityQueue<>();
        // 小根堆，维护较大的一半元素
         PriorityQueue<Integer> large;



        for (int i = 0; i < nums.length - k + 1; i++) {
            if (k % 2 == 0) {
                int left = (i + i + k - 1) / 2;
                int right = left + 1;
                res.add((nums[left] + nums[right]) / 2.0);
            } else {
                res.add(nums[(i + i + k - 1) / 2] * 1.0);
            }
        }
        double[] finalRes = new double[res.size()];
        for (int i = 0; i < res.size(); i++) {
            finalRes[i] = res.get(i);
        }
        return finalRes;
    }

    public static void main(String[] args) {
        Solution480 solution = new Solution480();
        int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
        int k = 3;
        System.out.println(Arrays.toString(solution.medianSlidingWindow(nums, k)));
    }
}
